#include <stdlib.h>
#include <stdio.h>

#include "fnct.h"

#define M 4
#define N 4
#define MAX 65536

void young_matrixify(TYPE **A, int i, int j, int m, int n){
	if(i < 0 || j < 0 || i >= m || j >= n)
		return;
	TYPE min = *((PTYPE)A+i*n+j);
	if(i == m-1 && j == n-1){
		return;
	} else if(i == m-1 && j < n-1){
		if(*((PTYPE)A+i*n+j) > *((PTYPE)A+i*n+j+1)){
			swap((PTYPE)A+i*n+j, (PTYPE)A+i*n+j+1);
			young_matrixify(A, i, j+1, m, n);	
		}
	} else if(i < m-1 && j == n-1){
		if(*((PTYPE)A+i*n+j) > *((PTYPE)A+i*n+n+j)){
			swap((PTYPE)A+i*n+j, (PTYPE)A+i*n+n+j);
			young_matrixify(A, i+1, j, m, n);	
		}
	} else if(i < m-1 && j < n-1){
		if(*((PTYPE)A+i*n+j+1) < min) min = *((PTYPE)A+i*n+j+1);
		if(*((PTYPE)A+i*n+n+j) < min) min = *((PTYPE)A+i*n+n+j);
		if(min == *((PTYPE)A+i*n+j+1)){
			swap((PTYPE)A+i*n+j, (PTYPE)A+i*n+j+1);
			young_matrixify(A, i, j+1, m, n);	
		}
		if(min == *((PTYPE)A+i*n+n+j)){
			swap((PTYPE)A+i*n+j, (PTYPE)A+i*n+n+j);
			young_matrixify(A, i+1, j, m, n);	
		}
	}
}

TYPE extract_min(TYPE **A, int row, int col){
	int m = row;
	int n = col;
	if(m < 0 || n < 0 || m > M || n > N)
		return MAX;
	TYPE ret = *((PTYPE)A);
	*((PTYPE)A) = *((PTYPE)A+m*n-1);
	*((PTYPE)A+m*n-1) = MAX;
	young_matrixify(A, 0, 0, m, n);
	return ret;
}

TYPE young_matrixify_back(TYPE **A, int i, int j, int n){
	TYPE max = *((PTYPE)A+i*n+j);
        if(i == 0 && j == 0) return;
        else if(i == 0 && j > 0){
                if(*((PTYPE)A+j-1) > *((PTYPE)A+j)){
                        swap((PTYPE)A+j-1,(PTYPE)A+j);
                        j--;
			young_matrixify_back(A,i,j,n);
                }
        }else if(j == 0 && i > 0){
                if(*((PTYPE)A+(i-1)*n) > *((PTYPE)A+i*n)){
                        swap((PTYPE)A+(i-1)*n,(PTYPE)A+i*n);
                        i--;
			young_matrixify_back(A,i,j,n);
                }
        }else if(i > 0 && j > 0){
                if(*((PTYPE)A+(i-1)*n+j) > max) max = *((PTYPE)A+(i-1)*n+j);
                if(*((PTYPE)A+i*n+j-1) > max) max = *((PTYPE)A+i*n+j-1);
                if(max == *((PTYPE)A+(i-1)*n+j)){ 
                        swap((PTYPE)A+i*n+j,(PTYPE)A+(i-1)*n+j);
			i--;
			young_matrixify_back(A,i,j,n);
                }
                if(max == *((PTYPE)A+i*n+j-1)){
			swap((PTYPE)A+i*n+j,(PTYPE)A+i*n+j-1);
			j--;
			young_matrixify_back(A,i,j,n);
		}
        }
}

TYPE young_insert(TYPE **A, int m, int n, TYPE x){
	int i=m-1,j=n-1;
	if(*((PTYPE)A+i*n+j) >= MAX) *((PTYPE)A+i*n+j) = x;
	else return x;
	young_matrixify_back(A, i, j, n);
}

/**
 * 这个函数可以有更好的实现方法，即从左下角开始比较
 **/
Boolean find_element(TYPE **A, int m, int n, TYPE x){
	int i=0,j=0;
	while(i < m - 1 && j < n - 1){
		if(x < *((PTYPE)A+i*n+j)) return FALSE;
		else if(x == *((PTYPE)A+i*n+j)) return TRUE;
		else{
			*((PTYPE)A+(i+1)*n+j)>*((PTYPE)A+i*n+j+1)?j++:i++;
		}
	}

	while(i < m){
		if(x < *((PTYPE)A+i*n+j)) return FALSE;
                else if(x == *((PTYPE)A+i*n+j)) return TRUE;
		else i++;
	}
	
	while(j < n){
		if(x < *((PTYPE)A+i*n+j)) return FALSE;
                else if(x == *((PTYPE)A+i*n+j)) return TRUE;
                else j++;
	}
}

int main(void){
	TYPE a[M][N] = {2, 4, 9, 12, 3, 5, 14, MAX, 8, 16, MAX, MAX, MAX, MAX, MAX, MAX};
	//打印数组a,可以看出它符合young氏矩阵的定义
	print_two_array((TYPE **)a, M, N); 
    	//第一次取出最小值
    	printf("%d\n",extract_min((TYPE **)a, M, N));
    	//打印取出最小值之后的young氏矩阵
	print_two_array((TYPE **)a, M, N); 
    	//再次取出最小值
    	printf("%d\n",extract_min((TYPE **)a, M, N));
    	//打印取出最小值之后的young氏矩阵
    	print_two_array((TYPE **)a, M, N);
	young_insert((TYPE **)a, M, N, 19);
	young_insert((TYPE **)a, M, N, 8); 
	print_two_array((TYPE **)a, M, N);
	printf("Exist 8?:%d\n",find_element((TYPE **)a, M, N, 8));
	printf("Exist 16:%d\n",find_element((TYPE **)a, M, N, 16));
	printf("Exist 88:%d\n",find_element((TYPE **)a, M, N, 88));
	exit(0);
}
